package 竞赛.NO_402;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 100316. 施咒的最大总伤害
 * # 中等
 * 创建时间： 2024-06-16 10:39
 **/
public class 施咒的最大总伤害_100316 {
    public long maximumTotalDamage(int[] power) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : power) {
            cnt.merge(x,1, Integer::sum);
        }
        int[] a = new int[cnt.size()];
        int i = 0;
        for (Integer k : cnt.keySet()) {
            a[i++] = k;
        }
        Arrays.sort(a);
        long[] cache = new long[cnt.size()];
        Arrays.fill(cache, -1);
        return dfs(a, cnt, cache, i-1);
    }

    long dfs(int[] a, Map<Integer, Integer> cnt, long[] cache, int i) {
        if (i < 0) {
        return 0;
        }
        if (cache[i] != -1) {
            return cache[i];
        }
        int j = i-1;
        while(j >= 0 && a[i] - a[j] <= 2) {
            j--;
        }
        cache[i] = Math.max(dfs(a, cnt, cache, i - 1), dfs(a, cnt, cache, j) + (long) a[i] * cnt.get(a[i]));
        return cache[i];
    }
}
